package org.example.number;

/**
 * 统计一个数有多少和素数
 *
 * @author 玄鸽
 * @since 2023/9/4
 */
public class SuShu {

    public static void main(String[] args) {
        System.out.println(bf(100));
        System.out.println(eratosthenes(100));
    }

    /**
     * 统计素数的个数
     *
     * @param n 总数
     * @return 个数
     */
    private static int bf(int n) {
        int count = 0;
        for (int i = 2; i < n; i++){
            count += isPrime(i) ? 1 : 0;
        }
        return count;
    }

    /**
     * 埃筛法统计素数
     *
     * @param x 总数
     * @return 个数
     */
    private static boolean isPrime(int x) {
        for (int i = 2; i < x; i++) {
            // 如果能整数，那就不是素数
            if (x % i == 0) {
                return false;
            }
        }

        return true;
    }

    private static int eratosthenes(int n) {
        // false
        boolean[] isPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                count++;
                for (int j = 2 * i; j < n; j+=i) {
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }

}
